// https://www.lintcode.com/problem/ugly-number-ii/

public class Solution {
    /**
     * @param n: An integer
     * @return: return a  integer as description.
     */
    public int nthUglyNumber(int n) {
        // write your code here
        int[] nums = new int[n];
        Arrays.fill(nums, 1);
        int i2 = 0, i3 = 0, i5 = 0;
        for (int i = 1; i < n; ++i) {
            int m2 = 2 * nums[i2];
            int m3 = 3 * nums[i3];
            int m5 = 5 * nums[i5];
            nums[i] = Math.min(Math.min(m2, m3), m5);
            i2 = (nums[i] >= m2) ? (i2 + 1) : i2;
            i3 = (nums[i] >= m3) ? (i3 + 1) : i3;
            i5 = (nums[i] >= m5) ? (i5 + 1) : i5;
        }
        return nums[n - 1];
    }
}